#define _CRT_SECURE_NO_WARNINGS 1
int exgcd(int a, int b, int& x, int& y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }

    int d = exgcd(b, a % b, x, y);
    int temp = x;
    x = y;
    y = temp - a / b * x;

    return d;
}